/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-07 20:55
 **/

public class quick_sort {

    private quick_sort(){}

    public static void sort(int[] arr){
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int l, int r){
        if (l >= r){
            return;
        }else {
            int p = partition(arr, l, r);
            sort(arr, l, p - 1);
            sort(arr, p + 1, r);
        }
    }

    private static int partition(int[] arr, int l, int r){
        // 选一个标志，将大于它的移到他的前面，小于它的移到他的后面
        int i = l + 1, j = r;
        while (true){
            while (i <= j && arr[i] < arr[l]){
                i ++;
            }
            while (i <= j && arr[j] > arr[l]){
                j --;
            }
            if (i >= j){
                break;
            }
            swap(arr, i, j);
            i ++;
            j --;
        }
        swap(arr, l, j);
        return j;
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] arr = {2,4,1,32,44,5,12,3,6767,76,3,45,1,245,54,23};
        sort(arr);
        for (int a:arr
        ) {
            System.out.println(a);
        }
    }
}
